package mao.leetcode.others;

public class leetcode337 {

    public int rob(TreeNode root) {
        if(root == null) return 0;
        HelpeNode newRoot = new HelpeNode(root);
        copyTree(root,newRoot);
        return helper(newRoot);
    }

    public int  helper(HelpeNode node ){
        if(node.flag) return node.robCount;
        if(node.left == null || node.right == null){
            node.robCount = node.innerNode.val;
            node.flag = true;
        }
        int money1=0,money2=0;
        money1=helper(node.left)+helper(node.right);
        if(node.left != null){
            money2+=helper(node.left.left)+helper(node.left.right);
        }
        if(node.right != null){
            money2+=helper(node.right.left)+helper(node.right.right);
        }
        node.robCount =  Math.max(node.innerNode.val+money2,money1);
        node.flag = true;
        return node.robCount;
    }

    public void copyTree(TreeNode root1,HelpeNode root2){
        if (root1.left != null) {
            HelpeNode newNode = new HelpeNode(root1.left);
            root2.left = newNode;
            copyTree(root1.left,root2.left);
        }
        if (root1.right != null){
            HelpeNode newNode = new HelpeNode(root1.right);
            root2.right = newNode;
            copyTree(root1.right,root2.right);
        }
    }

    public static class HelpeNode{
        public TreeNode innerNode;
        public HelpeNode left;
        public HelpeNode right;
        public boolean flag = false;
        public int robCount=0;

        public HelpeNode(TreeNode node){
            this.innerNode=node;
        }
    }

    public static class TreeNode {
     int val;
     TreeNode left;
     TreeNode right;
     TreeNode(int x) { val = x; }
  }
}
